Open systems interConnect (OSI) layer 3 forwarding devices such as internet protocol (IP) routers maintain a routing database and forwarding tables to control the forwarding of layer 3 packets. The routing database may be generated by participating in layer 3 routing protocols to obtain next hop information for received packets. The forwarding tables may be generated based on lookups in the routing table.
Participating in layer 3 routing protocols, such as Open Shortest Path First (OSPF), Border Gateway Protocol (BGP), Intermediate System to Intermediate System (IS-IS), Protocol Independent Multicast (PIM) Dense Mode (PIM-DM), PIM Sparse Mode (PIM-SM), Distance Vector Multicast Routing Protocol (DVMRP), and Core Based Trees (CBT) can consume a high percentage processor cycles of a layer 3 forwarding device, such as an IP router. Accordingly, IP routers typically have a management module that participates in these protocols and distributes routes learned from participating in the layer 3 routing protocols to input/output modules that actually forward packets. For reliability purposes, some layer 3 forwarding devices may include a backup management module to take over participation in layer 3 routing protocols in the event of failure of the main management module. The switching of control from the main management module to the backup management module is referred to as failover.
One goal of the failover mechanisms is to be hitless with regard to packet forwarding. As used herein, the term “hitless failover” refers to continuing packet forwarding for existing connections when the main management module on a layer 3 forwarding device fails. In some conventional layer 3 forwarding devices, failover mechanisms are not hitless. That is, when the main management module fails, the backup management module must be booted from scratch, and or it must learn routing table entries by participating in the layer 3 routing protocols. Packets on existing connections will be dropped or routed around the failed the device until the new main management module participates in the IP routing protocols to reestablish itself with other nodes in the network. Higher protocol layers running on end nodes are required to retransmit dropped packets. This type of restart can be referred to as “cold restart.” In light of the problems associated with cold restart, hitless restart mechanisms have been proposed. One hitless restart mechanism is proposed in Moy, J., Hitless OSPF Restart, draft-ietf-ospf-hitless-restart-02.text, February 2002 (hereinafter, “Moy”). According to Moy, an OSPF router attempting a hitless restart originates grace link state advertisements (LSAs) announcing the intention to perform a hitless restart and asking for a grace period. During the grace period, its neighbors continue to announce the restarting router in their LSAs as if it were operating normally, and packets are routed through the restarting router using its forwarding tables which are preserved during the restart. One problem with the solution proposed in Moy is that it requires an extension to the OSPF protocol in that routers adjacent to the restarting router must recognize the grace LSAs and give the restarting router a grace period to restart its OSPF protocol function.
Another hitless restart mechanism that has been proposed is Sangli et al., Graceful Restart Mechanism for BGP, draft-ietf-idr-restart-05.text (June 2002) (hereinafter, “Sangli”). Sangli proposes a graceful restart mechanism for BGP. BGP or border gateway protocol is a routing protocol for routers that are not in the same administrative domain. The graceful restart mechanism proposed in Sangli requires the router requesting to restart its BGP protocol to send a message to its BGP pairs indicating its ability to preserve its forwarding state during BGP restart. Like the solution proposed in Moy, the peer routers wait for a predetermined time period before removing the BGP router from their forwarding tables. Also like the solution proposed in Moy, the BGP restart mechanism proposed in Sangli requires that neighboring routers participate in extensions to the BGP protocol.
Another problem with the restart mechanisms proposed in both Sangli and Moy is that they only relate to specific routing protocols. A given router may run multiple protocols, requiring a separate restart mechanism for each protocol. A possible solution to this hitless restart problem is to run all of the routing protocols on the backup management module so that restart can occur seamlessly. However, running all of the routing protocols on the backup management module is processor-intensive and requires synchronization between the databases and protocol state machines of the main and backup management modules. Moreover, neither Moy nor Sangli discusses or presents a solution to the problem of linking hardware and software forwarding table entries after a re-start.
Accordingly, in light of these problems associated with conventional restart mechanisms, there exists a long felt need for improved methods and systems for hitless restart of layer 3 forwarding.